4.1 SOR 收敛

定理 i-4-1（充分条件） $0 < \omega < 2$ $\bm A$ $\bm A \bm x = \bm b$ 的 SOR 迭代法收敛.

证明

$\bm L_\omega = (\bm D - \omega \bm L)\inv ((1 - \omega) \bm D + \omega \bm U)$ $\lambda$ $\bm L_\omega \bm y = \lambda \bm y$ ，故

\begin{array}{rc} ((1 - ω) D + ω U) y = λ (D - ω L) y \\ \Rightarrow & (((1 - ω) D + ω U) y, y) = λ ((D - ω L) y, y) \\ \Rightarrow & λ = \frac{(D y, y) - ω (D y, y) + ω (U y, y)}{(D y, y) - ω (L y, y)} \end{array}

记

\begin{aligned} (D y, y) & = \sum_{i = 1}^{n} a_{i i} {| y_{i} |}^{2} \equiv σ > 0, \\ - (L y, y) & \equiv α + i β, \end{aligned}

$\bm A = \bm A\trans$ $\bm U = \bm L\trans$ ，于是

\begin{aligned} - (U y, y) & = - y^{T} U y = (L y)^{T} y = - (y, L y) = - \overset{―}{(L y, y)} = α - i β, \\ 0 & < (A y, y) = ((D - L - U) y, y) = σ + 2 α, \end{aligned}

从而

\begin{aligned} λ & = \frac{(σ - ω σ - α ω) + i ω β}{(σ + α ω) + i ω β}, \\ {| λ |}^{2} & = \frac{(σ - ω σ - α ω)^{2} + ω^{2} β^{2}}{(σ + α ω)^{2} + ω^{2} β^{2}}, \end{aligned}

$0 < \omega < 2$ ，分子不为零，且有

\begin{aligned} (σ - ω σ - α ω)^{2} - (σ + α ω)^{2} \\ = ω σ (σ + 2 α) (ω - 2) < 0, \end{aligned}

$\vqty{\lambda} < 1$ ，从而 SOR 迭代法收敛. 证毕.